A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form.
Certain devices within the network, referred to as routers, use routing protocols to exchange and accumulate topology information that describes the network. This allows a router to construct its own routing topology database of the network. Upon receiving an incoming data packet, the router examines keying information within the packet and forwards the packet in accordance with the topology information in the topology database.
Many routing protocols use flooding-based distribution mechanisms to announce topology information to routers within the network. These routing protocols typically rely on routing algorithms that require each of the routers to have synchronized routing topology information. That is, flooding-based routing protocols require that all routers in the routing domain store, to the routers' respective topology databases, all of the routing information that has been distributed according to the protocol. In this way, the routers are able to select routes that are consistent and loop-free. Further, the ubiquity of the routing information allows the flooding process to be reliable, efficient and guaranteed to terminate. In operation, each router typically maintains an internal topology (or “link-state”) database and scans the entire database at a defined interval to generate and output link state messages so as to synchronize the database to neighboring routers within the routing domain. In this way, link state is propagated across the entire routing domain and stored in full at each router within the domain.
For example, Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS) routing protocols are link state protocols that use link state messages to ensure their routing topology is synchronized with respect to available interfaces, metrics and other variables associated with network links. OSPF utilizes Link State Advertisements (LSAs) while IS-IS uses Link State Protocol Data Units (LSPs) to exchange information. A router generating a link state message typically floods the link state message throughout the network such that every other router receives the link state message. In network topologies where routers are connected by point-to-point connections, each router floods link state messages to adjacent routers reachable on each interface to ensure synchronization. For a network using multi-access media, such as an Ethernet network, the routers within the network flood the link state messages to all other routers connected to the network. In either case, the receiving routers construct and maintain their own network topologies using the link information received via the link state messages. IS-IS is specified in “Intermediate system to Intermediate system routing information exchange protocol for use in conjunction with the Protocol for providing the Connectionless-mode Network Service (ISO 8473),” ISO, ISO/IEC 10589:2002, the entire contents of which is incorporated herein by reference. OSPF is described in “OSPF Version 2,” IETF Network Working Group, Request for Comments 2828, April 1998, which is incorporated by reference in its entirety.
OSPF networks in an autonomous system (AS) may be administratively grouped into areas. Each area within an AS operates like an independent network and has a unique 32-bit area identifier (area ID), which functions like an Internet Protocol (IP) address. Area IDs are unique numeric identifiers, often expressed in dot-decimal notation, but they are not IP addresses. Within an area, the topology database contains only topology information for the area, LSAs are flooded only to routers within the area, and routers compute routes only within their respective areas. Sub-networks (“subnets”) are divided into other areas, which are connected to form the whole of the autonomous system.
The central area of an AS, called the backbone area, has a special function and is always assigned the area ID 0.0.0.0. (i.e., Area 0). All other networks or areas in the AS are directly connected to the backbone area by a router that has interfaces in more than one area. These connecting routers are called area border routers (ABRs).
Because all areas are adjacent to the backbone area, an OSPF router sends all traffic not destined for the router's own area through the backbone area. The ABRs in the backbone area are then responsible for transmitting the traffic through to the appropriate ABR to the destination area. The ABRs summarize the link-state records of each area and advertise destination address summaries to neighboring areas. The advertisements contain the area ID of the area in which each destination lies, so that packets are routed to the appropriate ABR.
An OSPF restriction requires all areas to be directly connected by physical or virtual links to the backbone area so that packets can be properly routed. All packets are routed first to the backbone area by default. Packets that are destined for an area other than the backbone area (“non-backbone areas”) are then routed from the receiving backbone area ABR to an appropriate backbone area ABR with an interface to the destination area and then on to the remote host within the destination area.